home *** CD-ROM | disk | FTP | other *** search
/ Graphics Plus / Graphics Plus.iso / msdos / viewers / gif_doc / compress.gif next >
Text File  |  1990-03-30  |  6KB  |  125 lines
  1. LZW compression used to encode/decode a GIF file by Bob Montgomery [73357,3140]
  2.  
  3. ENCODER
  4. Consider the following input data stream in a 4 color (A, B, C, D)  system.  
  5. We will build a table of codes which represent strings of colors. Each time 
  6. we  find a new string, we will give it the next code, and break it  into  a 
  7. prefix string and a suffix color. The symbols \ or --- represent the prefix 
  8. string, and / represents the suffix color. The first 4 entries in the table 
  9. are  the  4 colors with codes 0 thru 3, each of which represents  a  single 
  10. color.  The next 2 codes (4 and 5) are the clear code and the end of  image 
  11. code.  The first available code to represent a string of colors is 6.  Each 
  12. time  we  find  a new code, we will send the prefix for that  code  to  the 
  13. output data stream. 
  14.  
  15. A B A B A B A B B B A B A B A  A  C  D A C D A D  C A B A A A B A B .....
  16. \/\/---/-----/\/---/-------/\/ \/ \ /\/---/---/\ /\/-----/---/---/
  17. 6 7   8     9 10 11      12 13 14 15 16  17 18 19 20   21  22  23     Code
  18.     6    8      10    8                14  16        8    13  7       Prefix
  19.  
  20. The  encoder table is built from input data stream. Always start  with  the 
  21. suffix  of  last  code,  and  keep getting colors  until  you  have  a  new 
  22. combination.
  23.  
  24. Color     Code      Prefix    Suffix    String    Output
  25.  A        0                             -
  26.  B        1                             -
  27.  C        2                             -
  28.  D        3                             -
  29. Clear     4                             -
  30. End       5                             -
  31.  A \                A         A                   First color is a special case.
  32.  B /  \   6         A         B         AB        A
  33.  A |  /   7         B         A         BA        B
  34.  B |
  35.  A /  |   8         6         A         ABA       6
  36.  B    |
  37.  A    |
  38.  B \  /   9         8         B         ABAB      8
  39.  B /  |   10        B         B         BB        B
  40.  B    |
  41.  A |  /   11        10        A         BBA       10
  42.  B |
  43.  A |
  44.  B |
  45.  A /  \   12        9         A         ABABA     9
  46.  A \  /   13        A         A         AA        A
  47.  C /  \   14        A         C         AC        A
  48.  D \  /   15        C         D         CD        C
  49.  A /  |   16        D         A         DA        D
  50.  C    |
  51.  D |  /   17        14        D         ACD       14
  52.  A |
  53.  D /  \   18        16        D         DAD       16
  54.  C \  /   19        D         C         DC        D
  55.  A /  |   20        C         A         CA        C
  56.  B    |
  57.  A    |
  58.  A |  /   21        8         A         ABAA      8
  59.  A |
  60.  B /  |   22        13        B         AAB       13
  61.  A    |
  62.  B    /   23        7         B         BAB       7
  63.  
  64. The  resultant  output stream is: A B 6 8 B 10 9 A A C D 14 16 D C 8 ....  
  65. The  GIF encoder starts with a code length of 2+1=3 bits for 4  colors,  so 
  66. when  the code reaches 8 we will have to increase the code size to 4  bits. 
  67. Similarly,  when the code gets to 16 we will have to increse the code  size 
  68. to 5 bits, etc. If the code gets to 13 bits, we send a clear code and start 
  69. over.   See GIFENCOD.GIF for a flow diagram of the encoding  process.  This 
  70. uses a tree method to search if a new string is already in the table, which 
  71. is much simpler, faster, and easier to understand than hashing.
  72.  
  73. ===========================================================================
  74.  
  75. DECODER
  76.  
  77. We will now see if we can regenerate the original data stream and duplicate 
  78. the  table looking only at the output data stream generated by the  encoder 
  79. on the previous page. The output data stream is:
  80.  
  81.           A B 6 8 B 10 9 A A C D 14 16 D C 8 ....
  82.  
  83. The  docoding process is harder to see, but easier to implement,  than  the 
  84. encoding process. The data is taken in pairs, and a new code is assigned to 
  85. each  pair. The prefix is the left side of the pair, and the suffix is  the 
  86. color  that  the right side of the pair decomposes to from the  table.  The 
  87. decomposition  is done by outputing the suffix of the code, and  using  the 
  88. prefix  as the new code. The process repeats until the prefix is  a  single 
  89. color, and it is output too. The output of the decomposition is pushed onto 
  90. a  stack, and then poped off the stack to the display, which  restores  the 
  91. original  order that the colors were seen by the encoder. We will  go  thru 
  92. the  first  few entries in detail, which will hopefully  make  the  process 
  93. clearer. 
  94.      The  first pair is (A B), so the prefix of code 6 is A and the  suffix 
  95. is B, and 6 represents the string AB. The color A is sent to the display. 
  96.      The 2nd pair is (B 6), so the prefix of code 7 is B and the suffix  is 
  97. the  the last color in the decomposition of code 6. Code 6 decomposes  into 
  98. BA, so code 7 = BA, and has a suffix A. The color B is sent to the display.
  99.      The 3rd pair is (6 8) and the next code is 8. How can we decompose  8.  
  100. We  know that the prefix of code 8 is 6, but we don't know the suffix.  The 
  101. answer  is that we use the suffix of the prefix code; A in this case  since 
  102. the suffix of 6 is A. Thus, code 8 = ABA and has a suffix A. We decompose 6 
  103. to get BA, which becomes AB when we pop it off the stack to the display.
  104.      The 4th pair is (8 B), so code 9 has a prefix of 8 and a suffix of  B, 
  105. and  code  9  = ABAB. We output ABA to the stack, and pop  it  off  to  the 
  106. display as ABA.
  107.      The 5th pair is (B 10) and the next code is 10. The prefix of code  10 
  108. is  B  and the suffix is B (since the prefix is B). Code 10 =  BB,  and  we 
  109. output the prefix B to the display.
  110.      The  6th  pair is (10 9) and the next code is 11. Thus the  prefix  of 
  111. code  11 is 10 and the suffix is the last color in the decomposition of  9, 
  112. which is A.  Thus code 11 = BBA, And we output BB to the display.
  113.      So  far, we have output the correct colors stream A B AB ABA B  BB  to 
  114. the display, and have duplicated the codes 6 thru 11 in the encoder  table. 
  115. This  process  is  repeated for the whole data stream  to  reconstruct  the 
  116. original  color stream and build a table identical to the one built by  the 
  117. encoder.  We start the table with codes 0-5 representing the 4 colors,  the 
  118. clear  code, and the end code. When we get to code 8, we must  increse  the 
  119. code  size  to  5 bits, etc.  See GIFDECOD.GIF for a flow  diagram  of  the 
  120. decoding process.
  121.  
  122. I Hope this helps take some of the mystery out of LZW compression, which is
  123. really quite easy once you 'see' it.      Bob Montgomery
  124.  
  125.